#pragma once
#include <queue>
#include <vector>
#include <iostream>

namespace ns_priority_queue
{
    template <class T>
    class less
    {
    public:
        bool operator()(const T& t1, const T& t2)
        {
            return t1 < t2;
        }
    };

    template <class T>
    class greater
    {
    public:
        bool operator()(const T& t1, const T& t2)
        {
            return t1 > t2;
        }
    };

    template <class T, class V = std::vector<T>, class Cmp = std::less<T>>
    class priority_queue
    {
    private:
        void AdjustUp(int child)
        {
            Cmp cmp;
            int parent = (child - 1) / 2;
            while(child > 0)
            {
                if(cmp(_v[parent], _v[child]))
                //if(_v[parent] > _v[child])
                {
                    std::swap(_v[parent], _v[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        void Downjust(int parent)
        {
            Cmp cmp;
            int child = 2 * parent + 1;
            int n = size();
            while(child < n)
            {
                if(child + 1 < n && cmp(_v[child], _v[child + 1]))
                //if(child + 1 < n && _v[child] > _v[child+1])
                    ++child;
                if(cmp(_v[parent], _v[child]))
                //if(_v[parent] > _v[child])
                {
                    std::swap(_v[parent], _v[child]);
                    parent = child;
                    child = 2 * parent + 1;
                }
                else
                {
                    break;
                }
            }
        }
    public:
        priority_queue()
        {}

        void push(const T& val)
        {
            _v.push_back(val);
            AdjustUp(size()-1);
        }

        void pop()
        {
            std::swap(_v[0], _v[size()-1]);
            _v.pop_back();
            Downjust(0);
        }

        T& top() const
        {
            return _v[0];
        }

        bool empty() const
        {
            return size() == 0;
        }

        size_t size() const
        {
            return _v.size();
        }

        void Show()
        {
            for(const auto& e : _v)
            {
                std::cout << e << " ";
            }
            std::cout << std::endl;
        }

        ~priority_queue()
        {}
    private:
        V _v;
    };
}